Analytic Combinatorics

"If you can specify it, you can analyze it." Ph. Flajolet

Online course materials.

Click here for access to studio-produced lecture videos and associated lecture slides that provide an introduction to analytic combinatorics.

Textbook.

Analytic combinatorics is a branch of mathematics that aims to enable precise quantitative predictions of the properties of large combinatorial structures, by connecting via generating functions formal descriptions of combinatorial structures with methods from complex and asymptotic analysis. The textbook Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick is the definitive treatment of the topic. The full text of the book is available for download here and you can purchase a hardcopy at Amazon or Cambridge University Press.

Chapter 1: Combinatorial Structures and Ordinary Generating Functions introduces the symbolic method, where we define combinatorial constructions that we can use to define classes of combinatorial objects. The constructions are integrated with transfer theorems that lead to equations that define generating functions whose coefficients enumerate the classes. We consider numerous examples from classical combinatorics.
Chapter 2: Labeled Structures and Exponential Generating Functions considers labelled objects, where the atoms that we use to build objects are distinguishable. We use exponential generating functions EGFs to study combinatorial classes built from labelled objects. As in Lecture 1, we define combinatorial constructions that lead to EGF equations, and consider numerous examples from classical combinatorics.
Chapter 3: Combinatorial Parameters and Multivariate Generating Functions describes the process of adding variables to mark parameters and then using the constructions form Lectures 1 and 2 and natural extensions of the transfer theorems to define multivariate GFs that contain information about parameters. We concentrate on bivariate generating functions (BGFs), where one variable marks the size of an object and the other marks the value of a parameter. After studying ways of computing the mean, standard deviation and other moments from BGFs, we consider several examples in some detail.
Chapter 4: Complex Analysis, Rational and Meromorphic Asymptotics surveys basic principles of complex analysis, including analytic functions (which can be expanded as power series in a region); singularities (points where functions cease to be analytic); rational functions (the ratio of two polynomials) and meromorphic functions (the ratio of two analytic functions). The heart of the matter is complex integration and Cauchy's theorem, which relates coefficients in a function's expansion to its behavior near singularities. The discussion culminates in a general transfer theorem that gives asymptotic values of coefficients for meromorphic (and rational) functions.
Chapter 5: Applications of Rational and Meromorphic Asymptotics investigates applications of the general transfer theorem of the previous lecture to many of the classic combinatorial classes that we encountered in Lectures 1 and 2. Then we consider a universal law that gives asymptotics for a broad swath of combinatorial classes built with the sequence construction.
Chapter 6: Singularity Analysis of Generating Functions addresses the one of the jewels of analytic combinatorics: the Flajolet-Odlyzko theorem, where we find the domain of analyticity of the function near its dominant singularity, approximate using functions from standard scale, and then transfer to coefficient asymptotics term-by-term. This leads to universal laws giving coefficient asymptotics for the large class of GFs having singularities of the square-root and logarithmic type.
Chapter 7: Applications of Singularity Analysis develops application of the Flajolet-Odlyzko approach to universal laws covering combinatorial classes built with the set, multiset, and recursive sequence constructions. Then we consider applications to many of the classic combinatorial classes that we encountered in Lectures 1 and 2.
Chapter 8: Saddle-Point Asymptotics covers the saddle point method, a general technique for contour integration that also provides an effective path to the development of coefficient asymptotics for GFs with no singularities.
Chapter 9: Multivariate Asymptotics and Limit Laws introduces the multivariate approach that is needed to quantify the behavior of parameters of combinatorial structures.

Booksite.

(this page). Since both the full text of Analytic Combinatorics and a full set of studio-produced lecture videos are available online, this booksite contains just some selected exercises for reference within the online course.